package cn.chen.算法.查找;

import java.util.ArrayList;
import java.util.List;

/**
 * 插值查找：
 * 和二分查找一样，只是mid的计算方法不一样
 */
public class InsertValueSearch {

    public static void main(String[] args){

        int []arr=new int[100];
        for(int i=1;i<=100;i++)
            arr[i-1]=i;

        /*int index = insertValueSearch(arr, 1, 0, arr.length - 1);
        if(index!=-1)
            System.out.println("arr["+index+"]");
        else
            System.out.println("没有该元素");*/


        int [] a={1,2,3,4,4,4,4,4,4,4,4,5,6,7,8,80};
        int i = insertValueSearch(a, 4, 0, a.length - 1);
        if(i!=-1)
            System.out.println("arr["+i+"]");
        else
            System.out.println("没有该元素");

        List<Integer> list = insertValueSearchAll(a, 4, 0, a.length - 1);
        if(list!=null){

            for(Integer s:list)
                System.out.println("arr["+s+"]");
        }
        else
            System.out.println("没有该元素");


    }
    public static int insertValueSearch(int [] arr,int value,int head,int end){

        if(head>end||arr[head]>value||arr[end]<value)   // head>end、value小于最小的、value大于最大的，就直接退出
            return -1;

        // 新的mid的计算方法
        int mid=head+(end-head)*(value-arr[head])/(arr[end]-arr[head]);
        if(value<arr[mid])
            return insertValueSearch(arr,value,head,mid-1);
        else if(arr[mid]<value)
            return insertValueSearch(arr,value,mid+1,end);
        else
            return mid;
    }

    // 查找数据中与value相同的所有
    public static List<Integer> insertValueSearchAll(int [] arr, int value, int head, int end){

        List<Integer> index=null;
        if(head>end||arr[head]>value||arr[end]<value)   // head>end、value小于最小的、value大于最大的，就直接退出
            return index;

        // 新的mid的计算方法
        int mid=head+(end-head)*(value-arr[head])/(arr[end]-arr[head]);
        if(arr[mid]>value)
            index=insertValueSearchAll(arr,value,head,mid-1);
        else if(arr[mid]<value)
            index=insertValueSearchAll(arr,value,mid+1,end);
        else{

            index=new ArrayList<>();
            index.add(mid);
            int mmm=mid;
            // 往前遍历，直到没有相同的值
            while(arr[--mmm]==value)
                index.add(mmm);
            // 往后遍历，直到没有相同的值
            while(arr[++mid]==value)
                index.add(mid);
        }
        return index;
    }
}
